package leetcode.code1019;

import java.util.Stack;

import leetcode.helper.tree.ListNode;

public class Solution {
	public int[] nextLargerNodes(ListNode head) {
		ListNode node = head;
		int len = 0;
		while (node != null) {
			node = node.next;
			len++;
		}
		int[] ans = new int[len];
		node = head;
		int p = 0;
		Stack<int[]> stack = new Stack<>();
		while (node != null) {
			int val = node.val;
			while (!stack.isEmpty() && val > stack.peek()[0]) {
				int[] cur = stack.pop();
				ans[cur[1]] = val;
			}
			stack.add(new int[] { val, p });
			node = node.next;
			p++;
		}
		return ans;
	}
}
